{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #彩灯装饰记录 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: decorateRecord"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #彩灯装饰记录 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一棵圣诞树记作根节点为 <code>root</code> 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照从左到右的顺序返回每一层彩灯编号，每一层的结果记录于一行。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1694758674-XYrUiV-%E5%89%91%E6%8C%87%20Offer%2032%20-%20I_%E7%A4%BA%E4%BE%8B1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [8,17,21,18,null,null,6]\n",
    "<strong>输出：</strong>[[8],[17,21],[18,6]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>节点总数 &lt;= 1000</code></li>\n",
    "</ol>\n",
    "\n",
    "<p>注意：本题与主站 102 题相同：<a href=\"https://leetcode-cn.com/problems/binary-tree-level-order-traversal/\">https://leetcode-cn.com/problems/binary-tree-level-order-traversal/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,17,21,18,null,null,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        queue = deque([root])\n",
    "        total_ans = []\n",
    "        while queue:\n",
    "            level_len = len(queue)\n",
    "            ans = []\n",
    "            for _ in range(level_len):\n",
    "                curr = queue.popleft()\n",
    "                ans.append(curr.val)\n",
    "                if curr.left:\n",
    "                    queue.append(curr.left)\n",
    "                if curr.right:\n",
    "                    queue.append(curr.right)\n",
    "            total_ans.append(ans)\n",
    "\n",
    "        return total_ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        from collections import deque\n",
    "        queue = deque()\n",
    "        queue.append((root, 0))\n",
    "        ans = []\n",
    "        last_index = -1\n",
    "\n",
    "        while queue:\n",
    "            node, index = queue.popleft()\n",
    "            \n",
    "            if index != last_index:\n",
    "                ans.append([node.val])\n",
    "                last_index = index\n",
    "            else:\n",
    "                ans[-1].append(node.val)\n",
    "            \n",
    "            if node.left is not None:\n",
    "                queue.append((node.left, index + 1))\n",
    "            if node.right is not None:\n",
    "                queue.append((node.right, index + 1))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "      if not root:return []\n",
    "      que, ans = collections.deque(), []\n",
    "      que.append(root)\n",
    "      while que:\n",
    "        tmp = []\n",
    "        i = len(que)-1\n",
    "        while i>=0:\n",
    "          node = que.popleft()\n",
    "          tmp.append(node.val)\n",
    "          if node.left:que.append(node.left)\n",
    "          if node.right:que.append(node.right)\n",
    "          i -= 1\n",
    "        ans.append(tmp)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        q=collections.deque()\n",
    "        q.append(root)\n",
    "        q.append(None)\n",
    "        ans,sub_ans=[],[]\n",
    "        while True:\n",
    "            node=q.popleft()\n",
    "            if node:\n",
    "                sub_ans.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            else:\n",
    "                ans.append(sub_ans)\n",
    "                if len(q)==0: \n",
    "                    break\n",
    "                else:\n",
    "                    sub_ans=[]\n",
    "                    q.append(None)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            level = []\n",
    "            for _ in range(sz):\n",
    "                cur = q.popleft()\n",
    "                level.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            res.append(level)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        stack = collections.deque()\n",
    "        stack.append(root)\n",
    "        while stack :\n",
    "            nexti = []\n",
    "            for _ in range(len(stack)) :\n",
    "                node = stack.popleft()\n",
    "                nexti.append(node.val)\n",
    "                if node.left :\n",
    "                    stack.append(node.left)\n",
    "                if node.right :\n",
    "                    stack.append(node.right)\n",
    "            ans.append(nexti)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tem = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tem.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tem)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "      if not root:return []\n",
    "      que, ans = collections.deque(), []\n",
    "      que.append(root)\n",
    "      while que:\n",
    "        tmp = []\n",
    "        for _ in range(len(que)):\n",
    "          node = que.popleft()\n",
    "          tmp.append(node.val)\n",
    "          if node.left:que.append(node.left)\n",
    "          if node.right:que.append(node.right)\n",
    "        ans.append(tmp)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        ans = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            this = []\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                if cur.left: q.append(cur.left)\n",
    "                if cur.right: q.append(cur.right)\n",
    "                this.append(cur.val)\n",
    "            ans.append(this)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tem = []\n",
    "            for  _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tem.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tem)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        deuqe = [root]\n",
    "        res = []\n",
    "        flag = True\n",
    "        while deuqe:\n",
    "            tmp = []\n",
    "            for i in range(len(deuqe)):\n",
    "                node = deuqe.pop(0)\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    deuqe.append(node.left)\n",
    "                if node.right:\n",
    "                    deuqe.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\tdef decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\t\tif not root:\n",
    "\t\t\treturn []\n",
    "\t\tnode_list = []\n",
    "\t\tnode_list.append(root)\n",
    "\t\tresult = []\n",
    "\t\twhile node_list:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tfor i in range(len(node_list)):\n",
    "\t\t\t\tnode = node_list.pop(0)\n",
    "\t\t\t\ttemp.append(node.val)\n",
    "\t\t\t\tif node.left:\n",
    "\t\t\t\t\tnode_list.append(node.left)\n",
    "\t\t\t\tif node.right:\n",
    "\t\t\t\t\tnode_list.append(node.right)\n",
    "\t\t\tresult.append(temp)\n",
    "\t\treturn result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            curLevelArr = []\n",
    "            curLevelLen = len(queue)\n",
    "            for i in range(curLevelLen):\n",
    "                node = queue.popleft()\n",
    "                curLevelArr.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(curLevelArr)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            layer = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                layer.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(layer)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root :return []\n",
    "        res=[]\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            new_stack=[]\n",
    "            res_line=[]\n",
    "            for _ in range(len(stack)):\n",
    "                cur=stack.pop()\n",
    "                res_line.append(cur.val)\n",
    "                if cur.left: stack=[cur.left]+stack\n",
    "                if cur.right: stack=[cur.right]+stack\n",
    "            res.append(res_line)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,q=[],deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            temp=[]\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                temp.append(node.val)   \n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,q=[],deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            temp=[]\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                temp.append(node.val)   \n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for x in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        re=[]\n",
    "        stack=[[root]]\n",
    "        while stack:\n",
    "            box=[]\n",
    "            nodes=stack[-1]\n",
    "            rbox=[]\n",
    "            for node in nodes:\n",
    "                if node:\n",
    "                    rbox.append(node.val)\n",
    "                    if node.left:box.append(node.left)\n",
    "                    if node.right:box.append(node.right)\n",
    "            stack=stack[1:]\n",
    "            if box:\n",
    "                stack.append(box)\n",
    "            if rbox:re.append(rbox)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\tdef decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\t\tif not root:\n",
    "\t\t\treturn []\n",
    "\t\tnode_list = []\n",
    "\t\tnode_list.append(root)\n",
    "\t\tresult = []\n",
    "\t\twhile node_list:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tfor i in range(len(node_list)):\n",
    "\t\t\t\tnode = node_list.pop(0)\n",
    "\t\t\t\ttemp.append(node.val)\n",
    "\t\t\t\tif node.left:\n",
    "\t\t\t\t\tnode_list.append(node.left)\n",
    "\t\t\t\tif node.right:\n",
    "\t\t\t\t\tnode_list.append(node.right)\n",
    "\t\t\tresult.append(temp)\n",
    "\t\treturn result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        # 注意 root=[]的情况\n",
    "        if not root: return []\n",
    "        result, queue = [], collections.deque()\n",
    "\n",
    "        queue.append(root)\n",
    "        \n",
    "        while queue:\n",
    "            temp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            result.append(temp)\n",
    "    \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        else:\n",
    "            queue = [root]\n",
    "            output = []\n",
    "            while len(queue) != 0:\n",
    "                temp = []\n",
    "                nxt = []\n",
    "                for i in range(len(queue)):\n",
    "                    temp.append(queue[i].val)\n",
    "                    if queue[i].left:               \n",
    "                        nxt.append(queue[i].left)\n",
    "                    if queue[i].right:\n",
    "                        nxt.append(queue[i].right)\n",
    "#                queue.pop(0)\n",
    "                queue = nxt\n",
    "                output.append(temp)\n",
    "            return output\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> list[list[int]]:\n",
    "        res = []\n",
    "        deque = collections.deque()\n",
    "        if not root:\n",
    "            return []\n",
    "        deque.append(root)\n",
    "\n",
    "        while deque:\n",
    "            tmp = []\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    deque.append(node.left)\n",
    "                if node.right:\n",
    "                    deque.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res, tn = [], [root]\n",
    "        while tn:\n",
    "            r = []\n",
    "            for _ in range(len(tn)):\n",
    "                t = tn.pop(0)\n",
    "                r.append(t.val)\n",
    "\n",
    "                if t.left:\n",
    "                    tn.append(t.left)\n",
    "                if t.right:\n",
    "                    tn.append(t.right)\n",
    "            res.append(r)\n",
    " \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        list_a=[root]\n",
    "        res=[]\n",
    "        # print(len(list_a))\n",
    "        res.append(list_a)\n",
    "        level=0\n",
    "        # print(list_a)\n",
    "        # print(res)\n",
    "        while True:\n",
    "            list_a=[]\n",
    "            # print(res)\n",
    "            # print(res[level])\n",
    "            # print(len(res[level]))\n",
    "            for i in range(len(res[level])):\n",
    "                root=res[level][i]\n",
    "                # print('被执行了')\n",
    "                # tmp.append(root.val)\n",
    "                if root.left:\n",
    "                    list_a.append(root.left)\n",
    "                if root.right:\n",
    "                    list_a.append(root.right)\n",
    "                res[level][i]=root.val\n",
    "            if not list_a:\n",
    "                break\n",
    "            res.append(list_a)\n",
    "            level+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        else:\n",
    "            res,queue=[],collections.deque()\n",
    "            queue.append(root)\n",
    "            while queue:\n",
    "                tmp=[]\n",
    "                for i in range(len(queue)):\n",
    "                    j=queue.popleft()\n",
    "                    tmp.append(j.val)\n",
    "                    if j.left:\n",
    "                        queue.append(j.left)\n",
    "                    if j.right:\n",
    "                        queue.append(j.right)\n",
    "                res.append(tmp)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        queue = []\n",
    "        res = []\n",
    "        if not root:\n",
    "            return []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            n = len(queue)\n",
    "            for _ in range(n):\n",
    "                node = queue.pop(0)\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append([i for i in tmp])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res,queue=[],collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            for _ in range(len(queue)):\n",
    "                node=queue.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                   queue.append(node.left)             \n",
    "                if node.right:\n",
    "                   queue.append(node.right)              \n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res, queue = [], collections.deque()\n",
    "        if root: queue.append(root)\n",
    "        while queue:\n",
    "            r = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                r.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(temp)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        ans=[]\n",
    "        while len(q) !=0:\n",
    "            nodes=[]\n",
    "            tps=[]\n",
    "            while len(q)!=0:\n",
    "                node=q.popleft()\n",
    "                nodes.append(node)\n",
    "                tps.append(node.val)\n",
    "            ans.append(tps)\n",
    "            for node in nodes:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        row, res, queue = 0, [], collections.deque()\n",
    "        queue.append((0,root))\n",
    "        tmp = []\n",
    "        while queue:\n",
    "            if queue[0][1].left: queue.append((queue[0][0] + 1, queue[0][1].left))\n",
    "            if queue[0][1].right: queue.append((queue[0][0] + 1, queue[0][1].right))\n",
    "            if queue[0][0] == row:\n",
    "                tmp.append(queue[0][1].val)\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "                tmp = [queue[0][1].val]\n",
    "                row += 1\n",
    "            queue.popleft()\n",
    "        res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:    return []\n",
    "        res, row_values = [], []\n",
    "        que = []\n",
    "        cur_last, next_last = root, None\n",
    "\n",
    "        que.append(root)\n",
    "        while len(que) != 0:\n",
    "            node = que.pop(0)\n",
    "            row_values.append(node.val)\n",
    "            \n",
    "            if node.left:\n",
    "                que.append(node.left)\n",
    "                next_last = node.left\n",
    "            if node.right:\n",
    "                que.append(node.right)\n",
    "                next_last = node.right\n",
    "\n",
    "            if node == cur_last:\n",
    "                cur_last = next_last\n",
    "                res.append(row_values.copy())\n",
    "                row_values.clear()\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# root =\n",
    "#    [8,17,21,18,null,null,6]\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        \n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        re=[]\n",
    "        stack=[[root]]\n",
    "        while stack:\n",
    "            box=[]\n",
    "            nodes=stack[-1]\n",
    "            rbox=[]\n",
    "            for node in nodes:\n",
    "                if node:\n",
    "                    rbox.append(node.val)\n",
    "                    if node.left:box.append(node.left)\n",
    "                    if node.right:box.append(node.right)\n",
    "            stack=stack[1:]\n",
    "            if box:\n",
    "                stack.append(box)\n",
    "            if rbox:re.append(rbox)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        row, res, queue = 0, [], collections.deque()\n",
    "        queue.append((0,root))\n",
    "        tmp = []\n",
    "        while queue:\n",
    "            if queue[0][1].left: queue.append((queue[0][0] + 1, queue[0][1].left))\n",
    "            if queue[0][1].right: queue.append((queue[0][0] + 1, queue[0][1].right))\n",
    "            if queue[0][0] == row:\n",
    "                tmp.append(queue[0][1].val)\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "                tmp = [queue[0][1].val]\n",
    "                row += 1\n",
    "            queue.popleft()\n",
    "        res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res, queue = [], [root]\n",
    "        # queue = collections.deque([root])\n",
    "        while queue:\n",
    "            # node = queue.pop(0)\n",
    "            # 当前层打印循环\n",
    "            temp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                temp.append(node.val)\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        res = []\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp_q = []\n",
    "            new_res = []\n",
    "            while q:\n",
    "                top_node = q.pop(0)\n",
    "                if top_node.left:\n",
    "                    tmp_q.append(top_node.left)\n",
    "                if top_node.right:\n",
    "                    tmp_q.append(top_node.right)\n",
    "                new_res.append(top_node.val)\n",
    "            q = tmp_q\n",
    "            res.append(new_res)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        if not root:\n",
    "            return ans\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            n=len(q)\n",
    "            layer=[]\n",
    "            for i in range(n):\n",
    "                node=q.popleft()\n",
    "                layer.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(layer)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        queue=[]\n",
    "        if not root:\n",
    "            return []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            length=len(queue)\n",
    "            res.append([])\n",
    "            for i in range(length):\n",
    "                root=queue[0]\n",
    "                res[-1].append(root.val)\n",
    "                queue.remove(queue[0])\n",
    "                if root.left:\n",
    "                    queue.append(root.left)\n",
    "                if root.right:\n",
    "                    queue.append(root.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res, queue = [], deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res,queue=[[]],collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            for _ in range(len(queue)):\n",
    "                node=queue.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                   queue.append(node.left)             \n",
    "                if node.right:\n",
    "                   queue.append(node.right)              \n",
    "            res.append(temp)\n",
    "        return res[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,queue = [],collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:queue.append(node.left)\n",
    "                if node.right:queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        q1, q2 = [], []\n",
    "        if not root:\n",
    "            return []\n",
    "        q1 = [root]\n",
    "        res = []\n",
    "        while q1:\n",
    "            current = []\n",
    "            l = len(q1)\n",
    "            for i in range(l):\n",
    "                n = q1.pop(0)\n",
    "                if n:\n",
    "                    current.append(n.val)\n",
    "                    if n.left:q2.append(n.left)\n",
    "                    if n.right:q2.append(n.right)\n",
    "            res.append(current)\n",
    "            q1 = q2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root : return []\n",
    "        res , queue = [] , collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left : queue.append(node.left)\n",
    "                if node.right :queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res, tmpres, queue, tmp = [], [], deque(), deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            tmpres.append(node.val)\n",
    "            if node.left:\n",
    "                tmp.append(node.left)\n",
    "            if node.right:\n",
    "                tmp.append(node.right)\n",
    "            if not queue:   # 当层已清零\n",
    "                res.append(tmpres)\n",
    "                tmpres = []\n",
    "                while tmp:\n",
    "                    queue.append(tmp.popleft())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        from collections import deque\n",
    "        ret = []\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            tmp = []\n",
    "            for _ in range(n):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            ret.append(tmp)\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res,queue=[],collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        queue = [root]\n",
    "\n",
    "        while queue:\n",
    "            tmp_queue = []\n",
    "            tmp_res = []\n",
    "            while queue:\n",
    "                ptr = queue.pop(0)\n",
    "                if ptr:\n",
    "                    tmp_res.append(ptr.val)\n",
    "                    tmp_queue.append(ptr.left)\n",
    "                    tmp_queue.append(ptr.right)\n",
    "            queue = tmp_queue\n",
    "            if tmp_res:\n",
    "                res.append(tmp_res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            temp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        row, res, queue = 0, [], collections.deque()\n",
    "        queue.append((0,root))\n",
    "        tmp = []\n",
    "        while queue:\n",
    "            if queue[0][1].left: queue.append((queue[0][0] + 1, queue[0][1].left))\n",
    "            if queue[0][1].right: queue.append((queue[0][0] + 1, queue[0][1].right))\n",
    "            if queue[0][0] == row:\n",
    "                tmp.append(queue[0][1].val)\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "                tmp = [queue[0][1].val]\n",
    "                row += 1\n",
    "            queue.popleft()\n",
    "        res.append(tmp)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
